/*****************************************************************************
 *  ENTROPY - emerging network to reduce orwellian potency yield
 *
 *  Copyright (C) 2003 Juergen Buchmueller <pullmoll@stop1984.com>
 *
 *  This program is free software; you can redistribute it and/or modify
 *  it under the terms of the GNU General Public License as published by
 *  the Free Software Foundation; either version 2 of the License, or
 *  (at your option) any later version.
 *
 *  This program is distributed in the hope that it will be useful,
 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *  GNU General Public License for more details.
 *
 *  You should have received a copy of the GNU General Public License
 *  along with this program; if not, write to the Free Software Foundation,
 *  Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, USA
 *
 *	$Id: monoopt.c,v 1.3 2005/07/12 23:12:29 pullmoll Exp $
 *****************************************************************************/

#include "config.h"
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <dirent.h>
#include <errno.h>
#include <unistd.h>
#include <errno.h>
#include <sys/stat.h>
#include <sys/time.h>

#ifndef	MAXPATHLEN
#define	MAXPATHLEN	256
#endif

#define	CONFIGFILE	"entropy.conf"
#define	STOREPATH	"store"

#define	SHA1SIZE	20
#define	CHUNKSIZE	16384

/* This is really file system dependent; we use an approximation */
#define	BLOCKSIZE	512

/* same as src/store_mono.c */
#define	SEARCH_FRACT	256

#define	UNUSED		((size_t)-1)

static const char rotor[4] = {'|', '/', '-', '\\'};

typedef struct index_s {
	uint8_t sha1[SHA1SIZE];
	time_t atime;
}	index_t;
#define	INDEXSIZE	sizeof(index_t)

size_t chunks_in;
size_t chunks_out;
size_t chunks_set = 0;
size_t depth;
index_t *idx = NULL;
size_t *old = NULL;
size_t *new = NULL;
uint8_t fingerprint[16];
uint8_t null[SHA1SIZE] = {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0};

char *hexstr(uint8_t *src, size_t size)
{
	static char hexbuff[256];
	char *dst = hexbuff;
	size_t i;

	if (size >= sizeof(hexbuff)/2)
		size = sizeof(hexbuff)/2 - 1;

	for (i = 0; i < size; i++)
		dst += sprintf(dst, "%02x", src[i]);
	*dst = '\0';

	return hexbuff;
}

#define	SIZEk	((uint64_t)1000)
#define	SIZEK	((uint64_t)1024)
#define	SIZEm	((uint64_t)1000*1000)
#define	SIZEM	((uint64_t)1024*1024)
#define	SIZEg	((uint64_t)1000*1000*1000)
#define	SIZEG	((uint64_t)1024*1024*1024)

/*
 *	strtoul_KMG()
 *	convert a number to an unsigned long long (uint64_t).
 *	The number can have a multilplier appended to it:
 *	k = 1000
 *	K = 1024
 *	m = 1000000
 *	M = 1024*1024 = 1048576
 *	g = 1000000000
 *	G = 1024*1024*1024 = 1073741824
 */
uint64_t strtoul_KMG(const char *src)
{
	char *mult;
	uint64_t val;

	val = (uint64_t) strtoul(src, &mult, 0);
	if (NULL != mult) {
		while (*mult == '\t' || *mult == ' ')
			mult++;
		if (*mult == 'K')
			val *= SIZEK;
		else if (*mult == 'k')
			val *= SIZEk;
		else if (*mult == 'M')
			val *= SIZEM;
		else if (*mult == 'm')
			val *= SIZEm;
		else if (*mult == 'G')
			val *= SIZEG;
		else if (*mult == 'g')
			val *= SIZEg;
	}
	return val;
}

const char *round_KMG(uint64_t size)
{
#define	BUFSIZE	64
	static char buff[BUFSIZE];
	char *dst = buff;

	if (0 == size) {
		snprintf(dst,BUFSIZE,"0");
	} else if (size < SIZEK) {
		snprintf(dst,BUFSIZE,"%u", (unsigned)size);
	} else if (size < SIZEM) {
		if (0 == (size % SIZEK) && size < 100 * SIZEK) {
			snprintf(dst,BUFSIZE,"%uK", (unsigned)(size / SIZEK));
		} else if (0 == (size % SIZEk) && size < 100 * SIZEK) {
			snprintf(dst,BUFSIZE,"%uk", (unsigned)(size / SIZEk));
		} else {
			snprintf(dst,BUFSIZE,"%u.%uK",
				(unsigned)(size/SIZEK),
				(unsigned)((size%SIZEK)*10/SIZEK));
		}
	} else if (size < SIZEG) {
		if (0 == (size % SIZEM) && size < 100 * SIZEM) {
			snprintf(dst,BUFSIZE,"%uM", (unsigned)(size / SIZEM));
		} else if (0 == (size % SIZEm) && size < 100 * SIZEM) {
			snprintf(dst,BUFSIZE,"%um", (unsigned)(size / SIZEm));
		} else {
			snprintf(dst,BUFSIZE,"%u.%uM",
				(unsigned)(size/SIZEM),
				(unsigned)((size%SIZEM)*10/SIZEM));
		}
	} else {
		if (0 == (size % SIZEG) && size < 100 * SIZEG) {
			snprintf(dst,BUFSIZE,"%uG", (unsigned)(size / SIZEG));
		} else if (0 == (size % SIZEg) && size < 100 * SIZEg) {
			snprintf(dst,BUFSIZE,"%ug", (unsigned)(size / SIZEg));
		} else {
			snprintf(dst,BUFSIZE,"%u.%uG",
				(unsigned)(size/SIZEG),
				(unsigned)((size%SIZEG)*10/SIZEG));
		}
	}
	return buff;
}

uint8_t keyroute(uint8_t sha1[16])
{
	uint8_t x;
	size_t i;

	x = sha1[0];
	for (i = 1; i < SHA1SIZE; i++)
		x ^= sha1[i];
	x = (x >> 4) ^ x;
	return x % 16;
}

int store_index(const char *filename, size_t fno)
{
	FILE *fp = NULL;
	uint8_t *chunk = NULL;
	size_t i, f, offs, size, max = 0, used = 0, count[16];
	uint8_t fpr;

	if (NULL != idx) {
		free(idx);
		idx = NULL;
	}

	if (NULL != new) {
		free(new);
		new = NULL;
	}

	if (NULL != old) {
		free(old);
		old = NULL;
	}

	fp = fopen(filename, "rb");
	if (NULL == fp) {
		fprintf(stderr, "fopen('%s','rb') failed (%s)\n",
			filename, strerror(errno));
		return -1;
	}

	if (0 != fseek(fp, 0, SEEK_END)) {
		fprintf(stderr, "fseek('%s',0,SEEK_END) failed (%s)\n",
			filename, strerror(errno));
		return -1;
	}

	size = ftell(fp);
	chunks_in = size / (INDEXSIZE + CHUNKSIZE);
	printf("%s %u chunks", filename, (unsigned)chunks_in);
	if (0 != fseek(fp, 0, SEEK_SET)) {
		fprintf(stderr, "fseek('%s',0,SEEK_SET) failed (%s)\n",
			filename, strerror(errno));
		return -1;
	}
	if (0 == chunks_out) {
		chunks_out = chunks_in;
	} else {
		printf(", %u new", (unsigned)chunks_out);
	}

	size = chunks_in * INDEXSIZE;
	idx = (index_t *)calloc(chunks_in, INDEXSIZE);
	if (NULL == idx) {
		fprintf(stderr, "calloc(0x%x,0x%x) failed (%s)\n",
			(unsigned)chunks_in, INDEXSIZE, strerror(errno));
		return -1;
	}

	new = (size_t *)calloc(chunks_out, sizeof(size_t));
	if (NULL == new) {
		fprintf(stderr, "calloc(0x%x,0x%x) failed (%s)\n",
			(unsigned)chunks_out, sizeof(size_t), strerror(errno));
		return -1;
	}
	old = (size_t *)calloc(chunks_in, sizeof(size_t));
	if (NULL == old) {
		fprintf(stderr, "calloc(0x%x,0x%x) failed (%s)\n",
			(unsigned)chunks_in, sizeof(size_t), strerror(errno));
		return -1;
	}

	for (i = 0; i < chunks_in; i++)
		old[i] = UNUSED;
	for (i = 0; i < chunks_out; i++)
		new[i] = UNUSED;

	if (size != fread(idx, 1, size, fp)) {
		fprintf(stderr, "fread('%s',0x%x) failed (%s)\n",
			filename, (unsigned)size, strerror(errno));
		return -1;
	}

	chunk = calloc(CHUNKSIZE, sizeof(uint8_t));
	if (NULL == chunk) {
		fprintf(stderr, "calloc(0x%x,0x%x) failed (%s)\n",
			CHUNKSIZE, (unsigned)sizeof(uint8_t), strerror(errno));
		return -1;
	}

	memset(count, 0, sizeof(count));
	for (i = 0; i < chunks_in; i++) {

		if (0 == idx[i].atime)
			continue;

		f = idx[i].sha1[3] % depth;
		/* key in wrong file? */
		if (f != fno) {
			idx[i].atime = 0;
			continue;
		}

		old[i] = i;
		offs = size + INDEXSIZE * i;
		if (0 != fseek(fp, offs, SEEK_SET)) {
			fprintf(stderr, "fseek('%s',0x%x) failed (%s)\n",
				filename, (unsigned)offs, strerror(errno));
			return -1;
		}
		if (12 != fread(chunk, 1, 12, fp)) {
			fprintf(stderr, "fread('%s',0x%x) failed (%s)\n",
				filename, CHUNKSIZE, strerror(errno));
			return -1;
		}
		/* THROW AWAY OLD KEYS */
		if (0 == memcmp(chunk, "V2.0", 4) || 0 == memcmp(chunk, "V2.1", 4)) {
			idx[i].atime = 0;
			continue;
		}

		fpr = keyroute(idx[i].sha1);
		count[fpr] += 1;
		used++;
	}
	free(chunk);
	chunk = NULL;

	printf(", %d used (%d%%)\n", used, 100 * used / chunks_in);

	for (i = 0; i < 16; i++)
		if (count[i] > max)
			max = count[i];

	if (0 == max)
		max++;

	for (i = 0; i < 16; i++)
		fingerprint[i] = (uint8_t)(count[i] * 255 / max);

	printf("fingerprint: %s\n", hexstr(fingerprint, 16));

	fclose(fp);
	return 0;
}

int store_sort(void)
{
	size_t i, j, pos, left, search;
	uint8_t fpr;

	search = chunks_out / SEARCH_FRACT;

	/* pass 1: optimal positions, youngest keys, don't store mismatches */
	printf("pass 1: ");
	left = 0;
	for (i = 0; i < chunks_in; i++) {
		/* skip unused slots */
		if (UNUSED == old[i])
			continue;

		fpr = fingerprint[keyroute(idx[i].sha1)];
		/* bad match, skip for now */
		if (fpr < 0x20) {
			left++;
			continue;
		}

		pos = idx[i].sha1[0] | (idx[i].sha1[1] << 8);
		pos %= chunks_out;

		if (UNUSED == new[pos]) {
			/* copy to free slot */
			new[pos] = i;
			old[i] = UNUSED;
		} else {
			/* swap if idx[i] key is newer */
			if (idx[i].atime > idx[new[pos]].atime) {
				size_t tmp = new[pos];
				new[pos] = i;
				old[tmp] = tmp;
			}
			left++;
		}
		if (0 == (i % 1024)) {
			printf("%c\b", rotor[(i/1024)%4]);
			fflush(stdout);
		}
	}

	/* we're done if 'left' is zero */
	if (0 == left) {
		return 0;
	}

	/* pass 2: fill keys into non-optimal positions */
	printf("\rpass 2: ");
	left = 0;
	for (i = 0; i < chunks_in; i++) {
		/* skip unused slots */
		if (UNUSED == old[i])
			continue;

		fpr = fingerprint[keyroute(idx[i].sha1)];
		/* bad match, skip for now */
		if (fpr < 0x20) {
			left++;
			continue;
		}

		pos = idx[i].sha1[0] | (idx[i].sha1[1] << 8);
		pos %= chunks_out;

		/* find empty slot up to 'search' slots after pos */
		for (j = 1; j < search; j++) {
			pos = (pos + 1) % chunks_out;
			if (UNUSED == new[pos]) {
				new[pos] = i;
				old[i] = UNUSED;
				break;
			}
		}
		if (j >= search) {
			left++;
		}
		if (0 == (i % 1024)) {
			printf("%c\b", rotor[(i/1024)%4]);
			fflush(stdout);
		}
	}

	if (0 == left) {
		return 0;
	}

	/* pass 3: put remaining keys in completely wrong places. */
	printf("\rpass 3: ");
	for (i = 0; i < chunks_in; i++) {
		if (UNUSED == old[i])
			continue;

		pos = idx[i].sha1[0] | (idx[i].sha1[1] << 8);
		pos %= chunks_out;

		for (j = 0; j < chunks_out; j++) {
			pos = (pos + 1) % chunks_out;
			if (UNUSED == new[pos]) {
				new[pos] = i;
				old[i] = UNUSED;
				break;
			}
		}
		if (0 == (i % 1024)) {
			printf("%c\b", rotor[(i/1024)%4]);
			fflush(stdout);
		}
	}

	return 0;
}

int store_swap(const char *filename)
{
	char filetemp[MAXPATHLEN];
	uint8_t *chunk = NULL;
	FILE *fi = NULL, *fo = NULL;
	size_t i, size, offs;
	int old_pct = -1, new_pct = -1, rc = 0;

	sprintf(filetemp, "%s~", filename);

	chunk = (uint8_t *)calloc(CHUNKSIZE, sizeof(uint8_t));
	if (NULL == chunk) {
		fprintf(stderr, "calloc(0x%x,0x%x) failed (%s)\n",
			CHUNKSIZE, (unsigned)sizeof(uint8_t), strerror(errno));
		return -1;
	}

	fi = fopen(filename, "rb");
	if (NULL == fi) {
		fprintf(stderr, "fopen('%s','rb') failed (%s)\n",
			filename, strerror(errno));
		rc = -1;
		goto bailout;
	}

	fo = fopen(filetemp, "wb");
	if (NULL == fo) {
		fprintf(stderr, "fopen('%s','wb') failed (%s)\n",
			filetemp, strerror(errno));
		rc = -1;
		goto bailout;
	}

	size = chunks_out * INDEXSIZE;
	for (i = 0; i < chunks_out; i++) {
		index_t tmp;
		if (UNUSED == new[i]) {
			memset(&tmp, 0, sizeof(tmp));
		} else {
			tmp = idx[new[i]];
		}
		if (INDEXSIZE != fwrite(&tmp, 1, INDEXSIZE, fo)) {
			fprintf(stderr, "fwrite('%s',0x%x) failed (%s)\n",
				filetemp, (unsigned)INDEXSIZE, strerror(errno));
			rc = -1;
			goto bailout;
		}
	}

	for (i = 0; i < chunks_out; i++) {
		new_pct = 100 * i / chunks_out;
		if (old_pct != new_pct) {
			printf("%3d%%\b\b\b\b", new_pct);
			fflush(stdout);
			old_pct = new_pct;
		}
		/* empty slot? */
		if (UNUSED == new[i]) {
			memset(chunk, 0, CHUNKSIZE);
		} else {
			/* find chunk in idx_old */
			offs = size + CHUNKSIZE * new[i];
			if (0 != fseek(fi, offs, SEEK_SET)) {
				fprintf(stderr, "fseek('%s',0x%x) failed (%s)\n",
					filename, (unsigned)offs, strerror(errno));
				rc = -1;
				goto bailout;
			}
			if (CHUNKSIZE != fread(chunk, 1, CHUNKSIZE, fi)) {
				fprintf(stderr, "fread('%s',0x%x) failed (%s)\n",
					filename, CHUNKSIZE, strerror(errno));
				rc = -1;
				goto bailout;
			}
		}
		if (CHUNKSIZE != fwrite(chunk, 1, CHUNKSIZE, fo)) {
			fprintf(stderr, "fwrite('%s',0x%x) failed (%s)\n",
				filetemp, CHUNKSIZE, strerror(errno));
			rc = -1;
			goto bailout;
		}
	}

bailout:
	if (NULL != fi)
		fclose(fi);
	if (NULL != fo)
		fclose(fo);
	if (NULL != chunk)
		free(chunk);
	if (0 == rc) {
		if (0 != unlink(filename)) {
			fprintf(stderr, "unlink('%s') failed (%s)\n",
				filename, strerror(errno));
			return -1;
		}
		if (0 != rename(filetemp, filename)) {
			fprintf(stderr, "rename('%s','%s') failed (%s)\n",
				filetemp, filename, strerror(errno));
			return -1;
		}
		printf("100%%\n");
	}
	printf("\n");
	return rc;
}

int main(int argc, char **argv)
{
	char store[MAXPATHLEN];
	char filename[MAXPATHLEN];
	struct stat st;
	uint64_t size;
	uint64_t total;
	size_t fno;
	int i;

	strcpy(store, STOREPATH);
	i = 1;
	while (i < argc && argv[i][0] == '-') {
		if (0 == strcmp(argv[i], "-h") ||
			0 == strcmp(argv[i], "--help")) {
			fprintf(stderr, "usage: %s [options]\n", argv[0]);
			fprintf(stderr, "options can be one or more of:\n");
			fprintf(stderr, "-p|--path pathname\tpath to store.XX files\n");
			fprintf(stderr, "-s|--size size[KMG]\tnew size (number of files doesn't change)\n");
			exit(0);
			
		} else if (0 == strcmp(argv[i], "-p") ||
			0 == strcmp(argv[i], "--path")) {
			if (i + 1 >= argc) {
				fprintf(stderr, "Missing value for %s\n", argv[i]);
				exit(42);
			}
			++i;
			strcpy(store, argv[i]);
		}
		i++;
	}

	for (depth = 0, total = 0; depth < 256; depth++) {
		sprintf(filename, "%s/store.%02x", store, depth);
		if (0 != stat(filename, &st))
			break;
		total += st.st_size;
	}
	if (0 == depth) {
		fprintf(stderr, "No store files found (%s)\n",
			strerror(errno));
		exit(42);
	}
	printf("found %u store files %s\n",
		(unsigned)depth, round_KMG(total));

	i = 1;
	while (i < argc && argv[i][0] == '-') {
		if (0 == strcmp(argv[i], "-s") ||
			0 == strcmp(argv[i], "--size")) {
			if (i + 1 >= argc) {
				fprintf(stderr, "Missing value for %s\n", argv[i]);
				exit(42);
			}
			++i;
			size = strtoul_KMG(argv[i]);
			chunks_set = (size_t)(size / depth / CHUNKSIZE);
			if (chunks_set < 256 || chunks_set > 65536) {
				fprintf(stderr, "Impossible size %s (%d*%u chunks)\n",
					round_KMG(size), depth, chunks_set);
				exit(42);
			}
		}
	}

	for (fno = 0; fno < depth; fno++) {
		sprintf(filename, "%s/store.%02x", store, fno);
		if (0 != stat(filename, &st))
			break;
		/* new number of chunks (or old if chunks_set = 0) */
		chunks_out = chunks_set;
		if (0 != store_index(filename, fno))
			break;
		if (0 != store_sort())
			break;
		store_swap(filename);
	}

	return 0;
}
